//
//  Problem1824.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/13.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1824. 最少侧跳次数
 给你一个长度为 n 的 3 跑道道路 ，它总共包含 n + 1 个 点 ，编号为 0 到 n 。一只青蛙从 0 号点第二条跑道 出发 ，它想要跳到点 n 处。然而道路上可能有一些障碍。
 给你一个长度为 n + 1 的数组 obstacles ，其中 obstacles[i] （取值范围从 0 到 3）表示在点 i 处的 obstacles[i] 跑道上有一个障碍。如果 obstacles[i] == 0 ，那么点 i 处没有障碍。任何一个点的三条跑道中 最多有一个 障碍。
 比方说，如果 obstacles[2] == 1 ，那么说明在点 2 处跑道 1 有障碍。
 这只青蛙从点 i 跳到点 i + 1 且跑道不变的前提是点 i + 1 的同一跑道上没有障碍。为了躲避障碍，这只青蛙也可以在 同一个 点处 侧跳 到 另外一条 跑道（这两条跑道可以不相邻），但前提是跳过去的跑道该点处没有障碍。

 比方说，这只青蛙可以从点 3 处的跑道 3 跳到点 3 处的跑道 1 。
 这只青蛙从点 0 处跑道 2 出发，并想到达点 n 处的 任一跑道 ，请你返回 最少侧跳次数 。
 注意：点 0 处和点 n 处的任一跑道都不会有障碍。

 示例 1：
     输入：obstacles = [0,1,2,3,0]
     输出：2
     解释：最优方案如上图箭头所示。总共有 2 次侧跳（红色箭头）。
     注意，这只青蛙只有当侧跳时才可以跳过障碍（如上图点 2 处所示）。
 示例 2：
     输入：obstacles = [0,1,1,3,3,0]
     输出：0
     解释：跑道 2 没有任何障碍，所以不需要任何侧跳。
 示例 3：
     输入：obstacles = [0,2,1,0,3,0]
     输出：2
     解释：最优方案如上图所示。总共有 2 次侧跳。
 提示：
     obstacles.length == n + 1
     1 <= n <= 5 * 105
     0 <= obstacles[i] <= 3
     obstacles[0] == obstacles[n] == 0
 */
@objcMembers class Problem1824: NSObject {
    func solution() {
        print(minSideJumpsClear([0,1,2,3,0]))
        print(minSideJumpsClear([0,1,1,3,3,0]))
//        print(minSideJumps([0,2,1,0,3,0]))
//        print(minSideJumpsClear([0,2,1,0,3,0]))
    }
    
    /*
     动态规划  超时了，不做了
     1: 创建一个数组：dp[3][len]
     2: dp[1][i]: 从第1行的i点出发到达尾部的最小次数
     3: dp[1][i] = min(dp[0][i+1], dp[1][i+1], dp[2][i+1]) + 1
     */
    func minSideJumps(_ obstacles: [Int]) -> Int {
        var dp = Array(repeating: Array(repeating: -1, count: obstacles.count), count: 3)
        
        // 特例最后一行都是0
        dp[0][obstacles.count-1] = 0
        dp[1][obstacles.count-1] = 0
        dp[2][obstacles.count-1] = 0
        
        for i in (0..<obstacles.count-1).reversed() {
            for row in 1...3 {
                if obstacles[i] == row {    // 当前节点上有阻碍
                    continue
                }
                
                if obstacles[i+1] != row {   // 当前行的下一个节点没有障碍，直接走过去
                    dp[row-1][i] = dp[row-1][i+1]
                } else {
                    var lu = obstacles.count + 1
                    if row != 1, obstacles[i] != 1, dp[0][i+1] != -1 {
                        lu = min(lu, dp[0][i+1]+1)
                    }
                    if row != 2, obstacles[i] != 2, dp[1][i+1] != -1 {
                        lu = min(lu, dp[1][i+1]+1)
                    }
                    if row != 3, obstacles[i] != 3, dp[2][i+1] != -1 {
                        lu = min(lu, dp[2][i+1]+1)
                    }
                    
                    print(row, dp[0][i+1], dp[1][i+1], dp[2][i+1])
                    dp[row-1][i] = lu == obstacles.count + 1 ? -1 : lu
                }
            }
        }
        
        print(dp)
        return dp[1][0]
    }
    
    /*
     思路：
     当前节点有障碍物 => row = -1;
     当前节点没有障碍物：
         下一个节点没有障碍物 => 直接走过去 =>  row = nextRow
         下一个节点障碍物 => 需要跳转到另外2条路径 => 跳到另外2条没有障碍的路径 => row = min(nextRow1, nextRow2) + 1
     1: 创建3个变量lrow，存储下一个位置到最终位置的次数，创建3个变量row，求当前位置到最走位置的次数
     2: 如果当前节点有障碍物 row1 = obstacles[i] == 1 => -1
     3: 如果当前行的下一个节点没有障碍物, 直接走过去 row1 = lrow1 != -1 => lrow1
     4: 如果当前行的下一个节点有障碍物, 选另外2个节点跳过去 row1 = min(lrow2, lrow3) + 1
     5: 确保另外2个节点没有障碍物： lrow2 + (obstacles[i] == 2 ? obstacles.count : 0)
     */
    func minSideJumpsClear(_ obstacles: [Int]) -> Int {
        var lrow1 = 0, lrow2 = 0, lrow3 = 0
        var row1 = 0
        var row2 = 0
        var row3 = 0
        for i in (0..<obstacles.count-1).reversed() {
            
            row1 = obstacles[i] == 1 ? -1 : lrow1 != -1 ? lrow1 : (min(lrow2 + (obstacles[i] == 2 ? obstacles.count : 0), lrow3 + (obstacles[i] == 3 ? obstacles.count : 0)) + 1)
            row2 = obstacles[i] == 2 ? -1 : lrow2 != -1 ? lrow2 : (min(lrow1 + (obstacles[i] == 1 ? obstacles.count : 0), lrow3 + (obstacles[i] == 3 ? obstacles.count : 0)) + 1)
            row3 = obstacles[i] == 3 ? -1 : lrow3 != -1 ? lrow3 : (min(lrow1 + (obstacles[i] == 1 ? obstacles.count : 0), lrow2 + (obstacles[i] == 2 ? obstacles.count : 0)) + 1)
            
            lrow1 = row1
            lrow2 = row2
            lrow3 = row3
        }
        
        return row2
    }
}

/*
 [2, 2, -1, 0, 0, 0],
 [2, -1, 0, 0, 0, 0],
 [1, 1, 1, 1, -1, 0]]
 */
